import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountOfSmallerNumbersAfterSelfNew {
    int[] dp; // dp[i] 就表示当前元素的逆序对个数
    int[] index; // 记录 nums 元素的原始下标
    int[] tmpNums; // 归并下 nums 的辅助数组, 用于更改元素位置
    int[] tmpIndex; // index 的辅助数组, nums 元素如何变, index 所记录的元素的原始下标就如何变

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        dp = new int[n];
        index = new int[n];
        // 给 index 赋值, 每一个元素对应的就是 nums 元素的下标
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }

        tmpNums = new int[n];
        tmpIndex = new int[n];

        mergeSort(nums, 0, n-1);

        // 将dp表里面的元素依次添加进题目要求的list中
        // 吐槽一下, 直接返回一个数组不就行了, 非要搞一个list, 还需要我手动一个个add
        List<Integer> list = new ArrayList<>();
        for(int x : dp) {
            list.add(x);
        }
        return list;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if(left >= right) {
            // 序列没有元素或者只有一个元素, 选不出逆序对, 直接return
            return;
        }

        // 1.根据中间点分左右部分
        int mid = left + ((right - left) >> 1);
        // [left, mid]   [mid+1, right]
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        // 2.统计逆序对个数, 同时合并两个有序序列
        // (这俩操作是相辅相成的, 在我统计完逆序对个数的时候, 序列正好有序)
        // 本质上还是枚举出逆序对个数, 只不过是有方法的直接统计出一堆逆序对, 不需要一个个去比对
        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                // 元素位置如何变, index 就跟着如何变
                tmpIndex[i] = index[cur2];
                // 更改完成后, 两个下标往后走, 找寻下一个元素
                i++;
                cur2++;
            }else {
                // nums[cur1] > nums[cur2]
                dp[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }

        while(cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }

        while(cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        // 3.将辅助数组的元素放回原数组
        for(int j = 0; j < right - left + 1; j++){
            nums[j + left] = tmpNums[j];
            index[j + left] = tmpIndex[j];
        }
    }
}
